package algorithm.leetcode.I1to100;

import java.util.Stack;

/**
 * 暴力法是不可以的
 * 单调栈的用法
 * 入栈的元素是 height 数组的索引，原则是 height 数组对应元素严格递增
 * 出栈用来计算当前高度(出栈元素索引对应值) * 宽度(出栈元素索引-栈顶元素-1)
 */

public class Q84 {

    public int largestRectangleArea(int[] heights) {

        int maxArea = 0;
        int[] newHeights = new int[heights.length+2];
        // 添加两端哨兵,尾部添加0保证添加这个0后之前所有的元素都可以出栈
        for (int i = 0; i < newHeights.length; i++) {
            if (i == 0 || i == newHeights.length-1) newHeights[i] = 0;
            else newHeights[i] = heights[i-1];
        }

        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < newHeights.length; i++) {
            if (i != 0) {
                // height[i]比stack peek的都小,所以右侧固定为 i
                // 高度是当前 stack pop 出来的元素,宽度是 i - stack.peek() - 1
                while (!stack.isEmpty() && newHeights[i] < newHeights[stack.peek()]) {
                    int pop = stack.pop();
                    maxArea = Math.max(maxArea, (i - stack.peek() - 1) * newHeights[pop]);
                }
            }
            stack.push(i);
        }

        return maxArea;
    }

}
